home *** CD-ROM | disk | FTP | other *** search
/ Day Cry / Day Cry CD.bin / oh_towns / taropyon / splib / splib.lzh / PRG / LHX / HUF.C < prev    next >
C/C++ Source or Header  |  1994-02-04  |  8KB  |  492 lines
  1. /***********************************************************
  2.         huf.c -- new static Huffman
  3. ***********************************************************/
  4. #include    "lh386.h"
  5.  
  6. #include    <stdlib.h>
  7. #include    <dos.h>
  8. #include    "slidehuf.h"
  9.  
  10. #ifdef    __HIGHC__
  11. #    pragma    On(Print_reg_vars);
  12. #    pragma    On(Align_labels);
  13. #endif
  14.  
  15. #ifdef    __HIGHC__
  16. #    ifndef    PASCAL
  17. #        define    PASCAL    (_DEFAULT_CALLING_CONVENTION | _CALLEE_POPS_STACK)
  18. #    endif
  19. #endif
  20.  
  21. #ifdef    __HIGHC__
  22. #    pragma    Calling_convention(PASCAL);
  23. #endif
  24. static void write_pt_len(short n, short nbit, short i_special);
  25. static void write_c_len(void);
  26. static void encode_c(short c);
  27. static void encode_p(ushort p);
  28. static void send_block(void);
  29. static void read_pt_len(short nn, short nbit, short i_special);
  30. static void read_c_len(void);
  31. #ifdef    __HIGHC__
  32. #    pragma    Calling_convention();
  33. #endif
  34.  
  35.  
  36. #define NP (MAX_DICBIT + 1)
  37. #define NT (USHRT_BIT + 3)
  38. #define PBIT 4            /* smallest integer such that (1U << PBIT) > * NP */
  39. #define TBIT 5            /* smallest integer such that (1U << TBIT) > * NT */
  40. #define NPT 0x80
  41.  
  42. ushort        left[2 * NC - 1], right[2 * NC - 1];
  43. uchar        c_len[NC], pt_len[NPT];
  44. ushort        c_freq[2 * NC - 1], c_table[4096], c_code[NC], p_freq[2 * NP - 1],
  45.             pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
  46. static uchar *buf = NULL;
  47. static ushort bufsiz = 0;
  48. static ushort blocksize = 0;
  49.  
  50. /***** encoding *****/
  51.  
  52. static void count_t_freq(void)
  53. {
  54.     REG short    i;
  55.     short        n;
  56.  
  57.     for (i = 0; i < NT; i++)
  58.         t_freq[i] = 0;
  59.     n = NC;
  60.     while (n > 0 && c_len[n - 1] == 0)
  61.         n--;
  62.     i = 0;
  63.     while (i < n)
  64.     {
  65.         short    k;
  66.  
  67.         k = c_len[i++];
  68.         if (k == 0)
  69.         {
  70.             short    count;
  71.  
  72.             count = 1;
  73.             while (i < n && c_len[i] == 0)
  74.             {
  75.                 i++;
  76.                 count++;
  77.             }
  78.             if (count <= 2)
  79.                 t_freq[0] += count;
  80.             else if (count <= 18)
  81.                 t_freq[1]++;
  82.             else if (count == 19)
  83.             {
  84.                 t_freq[0]++;
  85.                 t_freq[1]++;
  86.             } else
  87.                 t_freq[2]++;
  88.         } else
  89.             t_freq[k + 2]++;
  90.     }
  91. }
  92.  
  93. static void write_pt_len(short n, short nbit, short i_special)
  94. {
  95.     REG short    i;
  96.  
  97.     while (n > 0 && pt_len[n - 1] == 0)
  98.         n--;
  99.     putbits(nbit, n);
  100.     i = 0;
  101.     while (i < n)
  102.     {
  103.         REG short    k;
  104.  
  105.         k = pt_len[i++];
  106.         if (k <= 6)
  107.             putbits(3, k);
  108.         else
  109.             putbits(k - 3, USHRT_MAX << 1);
  110.         if (i == i_special)
  111.         {
  112.             while (i < 6 && pt_len[i] == 0)
  113.                 i++;
  114.             putbits(2, i - 3);
  115.         }
  116.     }
  117. }
  118.  
  119. static void write_c_len(void)
  120. {
  121.     REG short    i;
  122.     short        n;
  123.  
  124.     n = NC;
  125.     while (n > 0 && c_len[n - 1] == 0)
  126.         n--;
  127.     putbits(CBIT, n);
  128.     i = 0;
  129.     while (i < n)
  130.     {
  131.         short        k;
  132.  
  133.         k = c_len[i++];
  134.         if (k == 0)
  135.         {
  136.             short    count;
  137.  
  138.             count = 1;
  139.             while (i < n && c_len[i] == 0)
  140.             {
  141.                 i++;
  142.                 count++;
  143.             }
  144.             if (count <= 2)
  145.             {
  146.                 for (k = 0; k < count; k++)
  147.                     putcode(pt_len[0], pt_code[0]);
  148.             } else if (count <= 18)
  149.             {
  150.                 putcode(pt_len[1], pt_code[1]);
  151.                 putbits(4, count - 3);
  152.             } else if (count == 19)
  153.             {
  154.                 putcode(pt_len[0], pt_code[0]);
  155.                 putcode(pt_len[1], pt_code[1]);
  156.                 putbits(4, 15);
  157.             } else
  158.             {
  159.                 putcode(pt_len[2], pt_code[2]);
  160.                 putbits(CBIT, count - 20);
  161.             }
  162.         } else
  163.             putcode(pt_len[k + 2], pt_code[k + 2]);
  164.     }
  165. }
  166.  
  167. static void encode_c(short c)
  168. {
  169.     putcode(c_len[c], c_code[c]);
  170. }
  171.  
  172. static void encode_p(ushort p)
  173. {
  174.     REG ushort    c, q;
  175.  
  176.     c = 0;
  177.     q = p;
  178.     while (q)
  179.     {
  180.         q >>= 1;
  181.         c++;
  182.     }
  183.     putcode(pt_len[c], pt_code[c]);
  184.     if (c > 1)
  185.         putbits(c - 1, p);
  186. }
  187.  
  188. static void send_block(void)
  189. {
  190.     REG ushort    i;
  191.     ushort        root, pos, size;
  192.  
  193.     root = make_tree(NC, c_freq, c_len, c_code);
  194.     size = c_freq[root];
  195.     putbits(16, size);
  196.     if (root >= NC)
  197.     {
  198.         count_t_freq();
  199.         root = make_tree(NT, t_freq, pt_len, pt_code);
  200.         if (root >= NT)
  201.         {
  202.             write_pt_len(NT, TBIT, 3);
  203.         } else
  204.         {
  205.             putbits(TBIT, 0);
  206.             putbits(TBIT, root);
  207.         }
  208.         write_c_len();
  209.     } else
  210.     {
  211.         putbits(TBIT, 0);
  212.         putbits(TBIT, 0);
  213.         putbits(CBIT, 0);
  214.         putbits(CBIT, root);
  215.     }
  216.     root = make_tree(NP, p_freq, pt_len, pt_code);
  217.     if (root >= NP)
  218.     {
  219.         write_pt_len(NP, PBIT, -1);
  220.     } else
  221.     {
  222.         putbits(PBIT, 0);
  223.         putbits(PBIT, root);
  224.     }
  225.     pos = 0;
  226.     for (i = 0; i < size; i++)
  227.     {
  228.         REG uchar    flags;
  229.  
  230.         if (i % CHAR_BIT == 0)
  231.             flags = buf[pos++];
  232.         else
  233.             flags <<= 1;
  234.         if (flags & (1U << (CHAR_BIT - 1)))
  235.         {
  236.             ushort        k;
  237.  
  238.             encode_c(buf[pos++] + (1U << CHAR_BIT));
  239.             k = buf[pos++] << CHAR_BIT;
  240.             k += buf[pos++];
  241.             encode_p(k);
  242.         } else
  243.             encode_c(buf[pos++]);
  244.         if (unpackable)
  245.             return;
  246.     }
  247.     for (i = 0; i < NC; i++)
  248.         c_freq[i] = 0;
  249.     for (i = 0; i < NP; i++)
  250.         p_freq[i] = 0;
  251. }
  252.  
  253. static ushort output_pos = 0, output_mask = 0;
  254.  
  255. void        output_st1(ushort c, ushort p)
  256. {
  257.     static ushort    cpos;
  258.  
  259.     if ((output_mask >>= 1) == 0)
  260.     {
  261.         output_mask = 1U << (CHAR_BIT - 1);
  262.         if (output_pos >= bufsiz - 3 * CHAR_BIT)
  263.         {
  264.             send_block();
  265.             if (unpackable)
  266.                 return;
  267.             output_pos = 0;
  268.         }
  269.         cpos = output_pos++;
  270.         buf[cpos] = 0;
  271.     }
  272.     buf[output_pos++] = (uchar) c;
  273.     c_freq[c]++;
  274.     if (c >= (1U << CHAR_BIT))
  275.     {
  276.         buf[cpos] |= output_mask;
  277.         buf[output_pos++] = (uchar) (p >> CHAR_BIT);
  278.         buf[output_pos++] = (uchar) p;
  279.         c = 0;
  280.         while (p)
  281.         {
  282.             p >>= 1;
  283.             c++;
  284.         }
  285.         p_freq[c]++;
  286.     }
  287. }
  288.  
  289. void       *alloc_buf(void)
  290. {
  291.     bufsiz = 0xFFF0u; /* 16 * 1024u; */
  292.     while ((buf = malloc(bufsiz)) == NULL)
  293.     {
  294.         bufsiz = (bufsiz / 10U) * 9U;
  295.         if (bufsiz < 4 * 1024U)
  296.             break;
  297.     }
  298.     return buf;
  299. }
  300.  
  301. void        encode_start_st1(void)
  302. {
  303.     REG int     i;
  304.  
  305.     for (i = 0; i < NC; i++)
  306.         c_freq[i] = 0;
  307.     for (i = 0; i < NP; i++)
  308.         p_freq[i] = 0;
  309.     output_pos = output_mask = 0;
  310.     init_putbits();
  311.     buf[0] = 0;
  312. }
  313.  
  314. void        encode_end_st1(void)
  315. {
  316.     if (!unpackable)
  317.     {
  318.         send_block();
  319.         putbits(CHAR_BIT - 1, 0);        /* flush remaining bits */
  320.     }
  321. }
  322.  
  323. /***** decoding *****/
  324.  
  325. static void read_pt_len(short nn, short nbit, short i_special)
  326. {
  327.     REG short    i, c, n;
  328.  
  329.     n = getbits(nbit);
  330.     if (n == 0)
  331.     {
  332.         c = getbits(nbit);
  333.         for (i = 0; i < nn; i++)
  334.             pt_len[i] = 0;
  335.         for (i = 0; i < 256; i++)
  336.             pt_table[i] = c;
  337.     } else
  338.     {
  339.         i = 0;
  340.         while (i < n)
  341.         {
  342.             c = bitbuf >> (16 - 3);
  343.             if (c == 7)
  344.             {
  345.                 ushort        mask = 1U << (16 - 4);
  346.                 while (mask & bitbuf)
  347.                 {
  348.                     mask >>= 1;
  349.                     c++;
  350.                 }
  351.             }
  352.             fillbuf((c < 7) ? 3 : c - 3);
  353.             pt_len[i++] = c;
  354.             if (i == i_special)
  355.             {
  356.                 c = getbits(2);
  357.                 while (--c >= 0)
  358.                     pt_len[i++] = 0;
  359.             }
  360.         }
  361.         while (i < nn)
  362.             pt_len[i++] = 0;
  363.         make_table(nn, pt_len, 8, pt_table);
  364.     }
  365. }
  366.  
  367. static void read_c_len(void)
  368. {
  369.     REG short    i, c, n;
  370.  
  371.     n = getbits(CBIT);
  372.     if (n == 0)
  373.     {
  374.         c = getbits(CBIT);
  375.         for (i = 0; i < NC; i++)
  376.             c_len[i] = 0;
  377.         for (i = 0; i < 4096; i++)
  378.             c_table[i] = c;
  379.     } else
  380.     {
  381.         i = 0;
  382.         while (i < n)
  383.         {
  384.             c = pt_table[bitbuf >> (16 - 8)];
  385.             if (c >= NT)
  386.             {
  387.                 ushort        mask = 1U << (16 - 9);
  388.                 do
  389.                 {
  390.                     if (bitbuf & mask)
  391.                         c = right[c];
  392.                     else
  393.                         c = left[c];
  394.                     mask >>= 1;
  395.                 } while (c >= NT);
  396.             }
  397.             fillbuf(pt_len[c]);
  398.             if (c <= 2)
  399.             {
  400.                 if (c == 0)
  401.                     c = 1;
  402.                 else if (c == 1)
  403.                     c = getbits(4) + 3;
  404.                 else
  405.                     c = getbits(CBIT) + 20;
  406.                 while (--c >= 0)
  407.                     c_len[i++] = 0;
  408.             } else
  409.                 c_len[i++] = c - 2;
  410.         }
  411.         while (i < NC)
  412.             c_len[i++] = 0;
  413.         make_table(NC, c_len, 12, c_table);
  414.     }
  415. }
  416.  
  417. ushort        decode_c_st1(void)
  418. {
  419.     REG ushort    j, mask;
  420.  
  421.     if (blocksize == 0)
  422.     {
  423.         blocksize = getbits(16);
  424.         read_pt_len(NT, TBIT, 3);
  425.         read_c_len();
  426.         read_pt_len(NP, PBIT, -1);
  427.     }
  428.     blocksize--;
  429.     j = c_table[bitbuf >> 4];
  430.     if (j < NC)
  431.         fillbuf(c_len[j]);
  432.     else
  433.     {
  434.         fillbuf(12);
  435.         mask = 1U << (16 - 1);
  436.         do
  437.         {
  438.             if (bitbuf & mask)
  439.                 j = right[j];
  440.             else
  441.                 j = left[j];
  442.             mask >>= 1;
  443.         } while (j >= NC);
  444.         fillbuf(c_len[j] - 12);
  445.     }
  446.     return j;
  447. }
  448.  
  449. ushort        decode_p_st1(void)
  450. {
  451.     REG ushort    j, mask;
  452.  
  453.     j = pt_table[bitbuf >> (16 - 8)];
  454.     if (j < NP)
  455.         fillbuf(pt_len[j]);
  456.     else
  457.     {
  458.         fillbuf(8);
  459.         mask = 1U << (16 - 1);
  460.         do
  461.         {
  462.             if (bitbuf & mask)
  463.                 j = right[j];
  464.             else
  465.                 j = left[j];
  466.             mask >>= 1;
  467.         } while (j >= NP);
  468.         fillbuf(pt_len[j] - 8);
  469.     }
  470.     if (j != 0)
  471.         j = (1U << (j